The present invention relates generally to memory management and more particularly to explicit memory management. Specifically, a method and apparatus are provided for memory management based upon characteristics of memory requested.
Computer programs are typically algorithms that manipulate data to compute a result. A block of memory to store data must first be allocated before the data can be manipulated. When the data is no longer needed, the block of the memory is then deallocated or freed. Allocation and deallocation of the block of memory is commonly referred to as memory management.
Some programming languages(i.e., C, Pascal, Ada, C++, . . . ) allow a programmer to explicitly control memory management. Some of these programming languages (i.e., C, Pascal, C++) require explicit memory management by a programmer when at compile-time: the life-time of a data structure is not known; the size of a data structure is not known; or, the life-time of the program region that allocates a data structure terminates before the life-time of the data structure. These memory allocators are sometimes referred to as dynamic storage allocators because memory must be explicitly managed when information is only known at run-time.
Typically, an operating system provides a memory management service to programming languages. An application may use this service to explicitly manage memory to allocate a block of memory from an unused store of memory known as the free store or the heap. This service is typically called a heap manager.
A heap manager allocates arbitrary size blocks of memory interspersed with requests in arbitrary order to deallocate already allocated blocks of memory. Typically, each allocated block of memory does not overlap other allocated blocks of memory and a heap manager allocates or deallocates only an entire block of storage independent of the type or values of data stored in the block. In some programming languages (i.e., C, Pascal, Ada, C++) the block of memory in which data is stored may not be reallocated to compact memory while the data is in use because the heap manager cannot find and update pointers to the block of memory if it is reallocated.
Many computer architectures incur a performance penalty for accessing unaligned storage of data in memory. Stored data is unaligned if a data type is not on an appropriate boundary in memory. For example, when the alignment requirement is a word of four bytes, stored data is xe2x80x9calignedxe2x80x9d when its starting address is divisible by four. The performance penalty for accessing unaligned memory may include additional instruction cycles, poor cache utilization, and/or the introduction of bubbles into the execution pipeline.
FIG. 1 illustrates an example of a block 100 of memory allocated by a heap manager for storing a data structure 102. The data structure 102 includes two character (char) type data units 104, 108 and one integer (int) type data unit 106. Each char type data unit 104, 108 requires one byte of storage and each int type data unit 106 requires four bytes (one word) of storage. The data units 104, 106, 108 are arranged in the data structure 102 in the order of char, int, char.
A compiler can provide a properly aligned data structure 102 by ensuring that the data structure 102 starts and ends on an alignment boundary. The alignment requirement corresponding to the data structure 102 is the largest size of any one of its data units 104, 106, 108. Thus, the alignment requirement corresponding to data structure 102 is four bytes because the int type data unit 106 has a size of four bytes and is larger than the char type data units 104, 108.
Each data unit 104, 106, 108 included in the data structure 102 is aligned according to the data structure 102 alignment requirement of four bytes. Thus, the char type data unit 104 is followed by three bytes of padding 105 and other char type data unit 108 is also followed by three bytes of padding 109. Thus, 12 bytes of memory are used to store the data units 104, 106, 108 which alone have a total size of only six bytes.
The heap manager allocates the block of memory 100 according to the heap manager""s alignment requirement. In order to align memory access for all possible memory requests, the heap manager""s alignment requirement equals the size of the largest data unit for all possible memory requests. In the example illustrated in FIG. 1, the heap manager""s alignment requirement is eight bytes (double word).
The block 100 of memory includes a header 111 which includes a header size 110 indicating the size of the allocated memory and a header padding 112. In this example, the header size 110 is four bytes and the header padding 112 is four bytes. The header padding 112 is necessary so the data structure 102 begins on an alignment boundary (double word). Internal fragmentation 114 of four bytes at the end of the block 100 of memory allows the block 100 to end on a double word alignment boundary.
Internal fragmentation and large headers may pollute memory with unused data which may result in poor memory utilization. For example, data cache and paging memory are finite resources. Unused data stored in a data cache or in a paging memory may force out used data which may result in higher costs when reaccessing the forced out data.
A method for improving memory utilization includes measuring an alignment requirement corresponding to each of a plurality of data structures. Storage of the plurality of data structures in a data memory is arranged based on the alignment requirements.
It is to be understood that both the foregoing general description and the following detailed description are exemplary, but are not restrictive, of the invention.